/*
	Copyright (c) 2008, Grant Jones <grant@podtronics.com>.
	All rights reserved.

	Redistribution and use in source and binary forms, with or
	without modification, are permitted provided that the following
	conditions are met:

		Redistributions of source code must retain the above copyright
		notice, this list of conditions and the following disclaimer.
		
		Redistributions in binary form must reproduce the above copyright
		notice, this list of conditions and the following disclaimer in
		the documentation and/or other materials provided with the
		distribution.
		
		Neither the name of the gxjones.com nor the names of its
		contributors may be used to endorse or promote products derived
		from this software without specific prior written permission.
	
	THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
	"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
	LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
	FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
	COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
	INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
	(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
	SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
	HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
	STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
	ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
	OF THE POSSIBILITY OF SUCH DAMAGE.
	
	http://www.opensource.org/licenses/bsd-license.php
*/

/*
 *  radixtree.c
 *  radixtree
 *
 *  Created by Grant Jones on 2/29/08.
 *
 */

#include "radixtree.h"
#include "radixtree_cache.h"

#ifdef RADIXTREE_LOCATE_STEPS
static int g_radixtree_locate_steps = 0;
static int g_radixtree_locate_calls = 0;
#endif

/* ************************************************************************
************************************************************************ */
/*!
	@function rt_prefix_compare
	@abstract compares key strings a and b
	@discussion a and b prefixes are compared.
	@param a key string
	@param b key string
	@param comp_len In use this is the minimum length of the two keys to
		compare
	@result the locaton where the two keys differ (0 : the strings have
		no common prefix)
*/
unsigned long rt_prefix_compare( const char *a, const char *b, unsigned long comp_len )
{
	unsigned long i;
	for( i = 0; i < comp_len; i ++ )
	{
		if( a[i] != b[i] )
			return i;
	}
	
	return i;
}

/* ************************************************************************
************************************************************************ */
/*!
	@function rt_locate_key
	@abstract locates the nearest tag location relating to key
	@discussion 
	@param rt 
	@param key The target key to locate
	@param last_step_loc Last known good starting point for the last tag
		visited
	@param key_left The left over portion of the key which differed from
		the available keys
	@param result Describes the result of the key search: 0 = no match
		found ( key_left and last_step_loc are still valid ); 1 = complete
		match was found (key_left should have size = 0); 2 = partial match
		key tag needs to be split.
	@result The last known good tag location
*/
off_t rt_locate_key( rtree_t *rt, rtvalue_t *key, size_t *last_step_loc, rtvalue_t *key_left, int *result )
{
	TagManagerEnumStruct tmes;
	off_t cur_loc = rt->list_cursor;	/* starts at an arbitrary tag location */
	off_t tag_loc = 0ULL;
	TagStruct *tag;
/*	TagHdrStruct tag_hdr;*/
	size_t prefix_start = 0;
	size_t prefix_len;

	key_left->data = key->data;
	key_left->size = key->size;
	
	*result = 0;	/* not found */
	*last_step_loc = 0;	/* last step location is the offset to last know good starting point */

#ifdef RADIXTREE_LOCATE_STEPS
	g_radixtree_locate_steps = 0;
	g_radixtree_locate_calls++;
#endif


#ifdef LOCATE_TRACE_OUTPUT
	printf("\nrt_locate_key: ["); print_len( key->data, key->size ); printf("]\n");
#endif

	for(;;)
	{
		prefix_len = key->size - prefix_start;
		
		tagm_beginEnumTags(rt->tms, &tmes, cur_loc);

		while( (tag = tagm_nextTag( rt->tms, &tmes, &tag_loc )) )
		{
			if( tag->hdr.bFlags & TAG_OVERFLOW )		/* ignore overflow tags */
				continue;
			if( tag->hdr.klen == 0 )
				continue;
			unsigned long r;
			unsigned long min_len = (tag->hdr.klen<prefix_len?tag->hdr.klen:prefix_len);
#ifdef LOCATE_TRACE_OUTPUT	
			printf("[");print_len( tag->key, min_len ); printf("]["); print_len( &((char *)key->data)[prefix_start], min_len ); printf("]\n");
#endif			
			r = rt_prefix_compare( (char *)tag->key, &((char *)key->data)[prefix_start], min_len );

			if( r == 0 )		// doesn't match at all
				continue;

			prefix_start += r;
			key_left->size = key->size - prefix_start;
			key_left->data = &((char *)key->data)[prefix_start];
#ifdef LOCATE_TRACE_OUTPUT				
			printf("key->size: %ld; key_left->size: %ld; r: %ld\n", (int)key->size, (int)key_left->size, (int)r );
#endif			
			if( r == prefix_len )
			{
				if( tag->hdr.klen > prefix_len )
				{
#ifdef LOCATE_TRACE_OUTPUT				
					printf("no match found, requires split (tag key is larger than target key) tag->hdr.klen : %d, prefix_len : %d\n", (int)tag->hdr.klen, (int)prefix_len );
#endif					
					*result = 2;	/* no match found, requires split (tag key is larger than target key)*/
				}
				else
				{
#ifdef LOCATE_TRACE_OUTPUT				
					printf("found complete match\n");
#endif					
					*result = 1;
				}
//				return tag_loc;
				cur_loc = tag_loc;
				tag = NULL;		/* signal stop looping */
				break;
			}
			else if( r < tag->hdr.klen )
			{
#ifdef LOCATE_TRACE_OUTPUT			
				printf("no match found, requires split (tag key is larger than target key)\n");
#endif				
				*result = 2;	/* no match found, requires split (tag key is larger than target key)*/
				//return tag_loc;
				cur_loc = tag_loc;
				tag = NULL;		/* signal stop looping */
				break;
			}
			else
			{
				// follow this branch
#ifdef LOCATE_TRACE_OUTPUT				
				printf("following branch\n");
#endif				

#ifdef RADIXTREE_LOCATE_STEPS
				g_radixtree_locate_steps++;
#endif

				*last_step_loc = prefix_start;
				
				cur_loc = tag_loc;
				break;
			}

		}

		tagm_endEnumTags(rt->tms, &tmes);

		/* the one exit point: */
		if(!tag)
			return cur_loc;
	}
}


/* ************************************************************************
************************************************************************ */
int rt_remove_overflow( rtree_t *rt, off_t parent_tag_loc )
{
	TagManagerEnumStruct tmes;
	TagStruct *tag;
	off_t tag_loc;
	int result = 0;	/* assume success */
	
	tagm_beginEnumTags(rt->tms, &tmes, parent_tag_loc);	
	while( (tag = tagm_nextTag( rt->tms, &tmes, &tag_loc )) )
	{
		if( !(tag->hdr.bFlags & TAG_OVERFLOW) )		/* ignore everything but overflow tags */
			continue;
		
		/* remove the data */
		if( tagm_unlinkTag( rt->tms, tag_loc ) )
		{
			result = -1;
			break;
		}
	}
	tagm_endEnumTags(rt->tms, &tmes);	


	return result;
}

/* ************************************************************************
************************************************************************ */
int rt_insert_keyed_tag( TagManagerStruct *tags, off_t root_loc, off_t *tag_loc,  unsigned char *key, size_t key_sz, unsigned char *data, size_t data_sz, unsigned char bFlags )
{
	TagStruct new_tag;
	
	memset( &new_tag, 0, sizeof(TagStruct) );
	
	new_tag.hdr.bFlags = bFlags;
	new_tag.hdr.dlen = data_sz;
	new_tag.data = data;
	new_tag.hdr.klen = key_sz;
	new_tag.key = key;
	
	return tagm_insertTag( tags, root_loc, &new_tag, tag_loc );
}

/* ************************************************************************
************************************************************************ */
int rt_split_tag( rtree_t *rt, off_t tag_loc, size_t crit_key_loc, off_t *new_tag_loc )
{
	TagManagerStruct *tags = rt->tms;
	int result = -1;		/* assume error */
	int tid = -1;			/* assume error */
	off_t parent_loc = 0;
	*new_tag_loc = 0;
	

	TagStruct *t = tagm_readTag( tags, tag_loc, 1 );
	if(!t || !t->key)
		goto cleanup;

	/* There can be no data for branch tag node */
	assert( t->hdr.dlen == 0 );		
	assert( t->hdr.klen > crit_key_loc );
	assert( crit_key_loc > 0 );
	
	parent_loc = t->hdr.parent;
	
	/*
	1. create a new child tag (new_tag_loc) of parent_loc
	2. change tag_loc key (save stuff before crit_key_loc, add it to the
		new tag)
	3. unlink tag_loc
	4. changeTagParent of tag_loc to new_tag_loc
	*/
	tid = tagmt_beginTransaction( tags );
	
	if(tid < 0)
		goto cleanup;

//	printf("insert parent_loc: %d\n", (int)parent_loc );
	
	/* 1. create a new child tag */
	if( rt_insert_keyed_tag( tags, parent_loc, new_tag_loc, t->key, crit_key_loc, NULL, 0ULL, 0x00 ) )
		goto cleanup;

	/* 2. change tag_loc key */

	/* TODO: after the insert the tag info may have changed so we need to
		get the new info. Better ways of doing this! */
	tagm_freeTag(t);
	t = tagm_readTag( tags, tag_loc, 1 );
	if(!t || !t->key)
		goto cleanup;
	/* end HACK */
	
	t->hdr.klen -= crit_key_loc;
		
	if( tagmt_pwrite(tags,&t->hdr,sizeof(TagHdrStruct), tag_loc ) != sizeof(TagHdrStruct) )
	{
		TAGM_ERROR(("couldn't %s (%s)\n", __FUNCTION__, strerror(errno) ));
		goto cleanup;
	}	
	if( tagmt_pwrite(tags,&t->key[crit_key_loc],t->hdr.klen, tag_loc+sizeof(TagHdrStruct) ) != t->hdr.klen )
	{
		TAGM_ERROR(("couldn't %s (%s)\n", __FUNCTION__, strerror(errno) ));
		goto cleanup;
	}		

	/* 3. unlink tag_loc */
	if( tagm_unlinkTag(tags, tag_loc) )
		goto cleanup;
	
	/* 4. changeTagParent of tag_loc to new_tag_loc */
	if( tagm_changeTagParent(tags, tag_loc, *new_tag_loc) )
		goto cleanup;
	
	/* commit transaction */
	result = tagmt_endTransaction( tags, tid );
	
	
cleanup:	
	/* Abort any mid-transaction failures: */
	if( result < 0 && tid > 0 )
		tagmt_abortTransaction( tags, tid );	
		
	/* free tag */
	tagm_freeTag(t);
	
	return result;
}




/* ************************************************************************
************************************************************************ */
int rt_get( rtree_t *rt, rtvalue_t *key, rtvalue_t *data )
{
	rtvalue_t key_left;
	int locate_result;
	size_t last_step_loc;
	off_t last_loc;
	assert( key->size > 0);
	
	last_loc = rt_cache_get_key( rt, key, &last_step_loc, &key_left, &locate_result );
	if( locate_result == 0 )
	{
		last_loc = rt_locate_key( rt, key, &last_step_loc, &key_left, &locate_result );

		if(locate_result == 0)		/* key wasn't found */
			return 1;
		
		if( locate_result == 2 )	/* close match to key was found */
		{
			printf("found a close match\n");
			return 1;
		}
		
		rt_cache_put_key(rt, key, last_loc);
	}

	TagManagerEnumStruct tmes;
	TagStruct *tag;
	off_t tag_loc;
	data->data = 0;
	data->size = 0;
	
	tagm_beginEnumTags(rt->tms, &tmes, last_loc);	
	while( (tag = tagm_nextTag( rt->tms, &tmes, &tag_loc )) )
	{
		if( !(tag->hdr.bFlags & TAG_OVERFLOW) )		/* ignore everything but overflow tags */
			continue;
		if( !tag->data )
			continue;
		
		/* we have an overflow tag w/ data in it */
		
		size_t sloc = data->size;
		data->size += tag->hdr.dlen;
		data->data = realloc( data->data, data->size );		/* fix me: realloc in this loop is of teh badness!11!!!11 */
		memcpy( &((char *)data->data)[sloc], tag->data, tag->hdr.dlen );
	}
	tagm_endEnumTags(rt->tms, &tmes);
	
#ifdef RADIXTREE_LOCATE_STEPS
	fprintf(stderr, "last locate steps taken: %ld\n", g_radixtree_locate_steps );
#endif	
	
	if( data->size == 0 )	/* tag carries no payload */
		return 1;
	
	return 0;
}

/* ************************************************************************
************************************************************************ */
int rt_put_raw( rtree_t *rt, rtvalue_t *key, rtvalue_t *data, int bRemoveOverflow )
{
	rtvalue_t key_left;
	int locate_result;
	off_t overflow_tag_loc, new_tag_loc;
	size_t last_step_loc;

	assert( key->size > 0 && data->size > 0);

	rt_cache_invalidate(rt);	/* invalidate cache */

	off_t last_loc = rt_locate_key( rt, key, &last_step_loc, &key_left, &locate_result );

/*	printf("key_left: %ld bytes, \"%s\"; last_loc: %ld; locate_result: %s \n", key_left.size, key_left.data, (int)last_loc, (locate_result==0?"wasn't found": (locate_result==1?"key already exists":"key requires split")) );*/
	
	if( locate_result == 2 )
	{
		off_t split_root_loc;
		size_t crit_byte_loc = (key_left.data - key->data) - last_step_loc;
/*		printf("crit_byte_loc: %ld\n", (int) crit_byte_loc );*/
		
		/* need to split a key! */
		if( rt_split_tag( rt, last_loc, crit_byte_loc, &split_root_loc ) )
		{
			printf("rt_split_tag failed\n");
			return -1;
		}	
	
		last_loc = split_root_loc;
		/* this check was added after testing revealed a edge-case where a root key is split to make
		** a branch for a key which the prefix is the same as the original key but smaller */
		if( key_left.size == 0 )
			locate_result = 1;	/* the parent will contain the data */
		else
			locate_result = 0;	/* we need to add a new child */
	}
	
	if(locate_result == 0)
	{
		/* wasn't found, insert at last_loc */
		if( rt_insert_keyed_tag( rt->tms, last_loc, &new_tag_loc, key_left.data, key_left.size, NULL, 0ULL, 0x00 ) )
			return -1;
		if( rt_insert_keyed_tag( rt->tms, new_tag_loc, &overflow_tag_loc, NULL, 0ULL, data->data, data->size, TAG_OVERFLOW ) )
			return -1;
	}
	else
	{
		/* key already exists : remove all overflow pages */
		
		if( bRemoveOverflow )
		{
			if( rt_remove_overflow( rt, last_loc ) )
				return -1;
		}
		if( rt_insert_keyed_tag( rt->tms, last_loc, &overflow_tag_loc, NULL, 0ULL, data->data, data->size, TAG_OVERFLOW ) )
			return -1;
	}

	return 0;	/* success */
}
int rt_put( rtree_t *rt, rtvalue_t *key, rtvalue_t *data )
{
	return rt_put_raw( rt, key, data, 1 );
}
/* ************************************************************************
************************************************************************ */
int rt_del( rtree_t *rt, rtvalue_t *key, int bOverflow )
{
	rtvalue_t key_left;
	int locate_result;
	size_t last_step_loc;
	int result = 0;				/* assume success */
	assert( key->size > 0);

	off_t last_loc = rt_locate_key( rt, key, &last_step_loc, &key_left, &locate_result );

	if(locate_result == 0)		/* key wasn't found */
		return 1;
	
	if( locate_result == 2 )	/* close match to key was found */
		return 1;
	
	rt_cache_invalidate(rt);	/* invalidate cache */
	
	result = rt_remove_overflow(rt, last_loc);
	
	if( result != 0 || bOverflow )	/* exit early with the error */
		return result;
		
	/* now that we removed all data, see if the last_loc tag has no child, if so remove it */

	TagStruct *t = tagm_readTag( rt->tms, last_loc, 0 );
	if(!t)
		return -1;
	
	if( t->hdr.first == 0ULL )
	{
		assert( t->hdr.last == 0ULL );
		
		/* tag has no children, effectively a leaf node. It is safe to remove this tag */
		result = tagm_unlinkTag( rt->tms, last_loc );
	}

	/* release tag */
	tagm_freeTag(t);

	return result;
}

/* ************************************************************************
************************************************************************ */
/*!
	@function rt_app
	@abstract Appends data to a key's data
	@discussion Since tag data is stored as overflow tags appending data
		is a very efficient operation.
	@param rt
	@param key
	@param append_data 
	@result
*/
int rt_app( rtree_t *rt, rtvalue_t *key, rtvalue_t *append_data )
{
	return rt_put_raw(rt, key, append_data, 0);
}

/*!
	@function rt_root_get
	@abstract retrieves tag data and location of tag specified by key
	@discussion beware: linear search
	@param rt tree root to search
	@param key the key in
	@param data data->data contains a buffer large enough to hold the key's
		associated value; data->size is checked to make sure the buffer
		meets this requirement.
	@result on success the location where the tag was found; on failure
		this is zero (which IS a valid location but it is the root item
		which cannot be retrieved in this way)
*/
off_t rt_root_get( rtree_t *rt, rtvalue_t *key, rtvalue_t *data )
{
	TagStruct *tag;
	TagManagerEnumStruct tmes;
	off_t tag_loc;
	
	tagm_beginEnumTags(rt->tms, &tmes, /*0ULL*/rt->list_cursor );

	while( (tag = tagm_nextTag( rt->tms, &tmes, &tag_loc )) )
	{
		if( tag->hdr.bFlags & TAG_OVERFLOW || tag->hdr.bFlags & TAG_DELETED )		/* ignore overflow & deleted tags */
			continue;
		if( tag->hdr.klen != key->size )
			continue;
		
		if( memcmp(tag->key, key->data, key->size ) == 0 )
		{
			if( data->data != NULL )
			{
				assert( data->size == tag->hdr.dlen );
				memcpy( data->data, tag->data, data->size );
			}
			else
			{
				data->size = tag->hdr.dlen;
			}
			break;
		}
	}
	tagm_endEnumTags(rt->tms, &tmes );
	
	return (tag?tag_loc:0ULL);
}

/*!
	@function rt_root_set
	@abstract defines a branch off the root specified by key_name
	@discussion Used to define meta data for a tree
	@param rt the tree
	@param key_name the null-terminated key name
	@param data the data to store for the key
	@param tag_loc on success contains the new/old location of the tag
	@result 0 on success; failure otherwise
*/
int rt_root_set( rtree_t *rt, rtvalue_t *key, rtvalue_t *data, off_t *tag_loc )
{
	rtvalue_t existing_data;
	existing_data.data = NULL;
	existing_data.size = 0;
	*tag_loc = rt_root_get( rt, key, &existing_data );
	TagStruct new_tag;
	assert( *tag_loc == 0ULL || existing_data.size == data->size );
	assert( data->size > 0 );	/* must have substance */
	
	if( *tag_loc == 0ULL )
	{
		memset( &new_tag, 0, sizeof(TagStruct) );

		new_tag.key = (unsigned char *)key->data;
		new_tag.data = data->data;
		new_tag.hdr.klen = key->size;
		new_tag.hdr.dlen = data->size;
	
		return tagm_insertTag(rt->tms, /*0ULL*/rt->list_cursor, &new_tag, tag_loc);
	}
	else
	{
		if( tagmt_pread(rt->tms, &new_tag.hdr, sizeof(TagHdrStruct), *tag_loc ) != sizeof(TagHdrStruct) )
			return -1;

		if( tagmt_pwrite(rt->tms,data->data,data->size, (*tag_loc)+new_tag.hdr.klen+sizeof(TagHdrStruct) ) != new_tag.hdr.dlen )
			return -1;
	}
	
	return 0;
}

/* ************************************************************************
************************************************************************ */

/*!
	@function rtree_use
	@abstract selects a tag to use as the root for the next operations
	@discussion
	@param rt
	@param key keyname of length key_sz, may be NULL in which case
		   the list_cursor is set to the real root (0).
	@param key_sz 
	@result 0 on success; failure otherwise
*/
int rtree_use( rtree_t *rt, const char *key, size_t key_sz )
{
	unsigned char scratch[256];
	rtvalue_t data = { 256, scratch };
	rtvalue_t key_val = { key_sz, (void *)key };
	off_t tag_loc;
	memset( scratch, 0, 256 );
	
	if( key == NULL )
	{
		rt->list_cursor = 0ULL;
		return 0;
	}
	
	/* TODO: major performance improvement can be had by caching the get operation */
	tag_loc = rt_root_get( rt, &key_val, &data );

	if( tag_loc == 0ULL )
	{
#ifdef DEBUG
		printf("unable to locate domain root location \"");
		fwrite(key, key_sz, 1, stdout);
		printf("\", creating\n" );
#endif		
		rt_root_set( rt, &key_val, &data, &tag_loc );
		assert( tag_loc != 0ULL );
	}

	/* only set list_cursor here: */
	rt->list_cursor = tag_loc;	
	return 0;
}

/*!
	@function rtree_open
	@abstract Opens a rtree file
	@discussion 
	@param rt
	@param file
	@param flags
	@result 0 on success; failure otherwise
*/
int rtree_open( rtree_t *rt, const char *file, int flags )
{
	rt->key_cache = cmap_new(NULL);
	rt->max_cache_items = 4;
//	rt_cache_invalidate( rt );
	
	rt->tms = tagm_open( file );
	if(!rt->tms)
		goto done;

	if( flags & RT_FLAG_FSYNC )
		rt->tms->enable_fsync = 1;
	
	/* any operations that don't call 'use' before operating will
	** be performed on the _trash branch */
	rtree_use( rt, NULL, 0 );			/* position table cursor at root */
	rtree_use( rt, "_trash", 6 );		/* position table cursor at root */
	
/*	printf("current root loc: %ld\n", (long int)rt->list_cursor );	*/

done:
	return (rt->tms==NULL?-1:0);
}
/*!
	@function rtree_close
	@abstract closes a tree
	@discussion will effectively abort any pending transactions
	@param rt the tree
	@result 0 on success
*/
int rtree_close( rtree_t *rt )
{
	tagm_close(rt->tms);
	cmap_destroy(rt->key_cache);
	return 0;
}




